\documentclass[a4paper]{D:/repositories/MyDGP/latex/PaperReadingLog}
\usepackage{caption}
\usepackage{overpic}
\usepackage{float}

\usepackage{enumitem} 
\usepackage{amsfonts,amssymb,amsmath}

\usepackage{algorithm}%%算法伪代码，支持中文
\usepackage{algorithmic}
\setmainfont{Arial}

\begin{document}

\PaperInfo
{2.基于信赖域的无约束问题的最优化方法}
{朱}
{天宇}
{}

\section{信赖域方法}
信赖域方法首先定义当前迭代点的一个邻域
$$
\Omega_k=\{\mathrm{x}\in\mathbb{R}^n | \lVert \mathrm{x}-\mathrm{x}^k \lVert \le e_k \}
$$

这里，$\lVert \bullet \lVert$可以是任意意义的模；$e_k$是信赖域半径；$\Omega_k$称为信赖域。

在这个邻域内，二次模型$q^k(\mathrm{s})$是目标函数$f(\mathrm{x})$的一个合适的近似，在此信赖域中极小化二次模型后得到的近似极小点$\mathrm{s}^k$，并且取$\mathrm{x}^{k+1}=\mathrm{x}^k+\mathrm{s}^k$。

\textbf{信赖域拥有全局收敛性，并且不要求Hessian矩阵正定。}

\section{算法流程}

介绍算法之前，首先要介绍\textbf{信赖域子问题}。

\subsection{信赖域子问题}
信赖域方法无需求解每一次迭代的方向，而是求解一个带约束的子问题：

$$
\begin{aligned}
    \min&\quad q^k(\mathrm{s})=f(\mathrm{x}^k)+(\mathrm{g}^k)^\top\mathrm{s}+\frac{1}{2}\mathrm{s}^\top\mathrm{B}_k\mathrm{s}\\
    s.t.&\quad \lVert \mathrm{s} \lVert\le e_k
\end{aligned}
$$

这里，$\mathrm{s}=\mathrm{x}-\mathrm{x}^k$，$\mathrm{g}^k=\nabla f(\mathrm{x}^k)$，$\mathrm{B}_k$是对称阵，可以是Hessian矩阵或者其近似，比如拟牛顿方法中的近似矩阵。等号右边是一个关于$\mathrm{s}$或者是关于$\mathrm{x}$的二次函数。在求出最小的点对应的$\mathrm{s}$之后，更新$\mathrm{x}^{k+1}=\mathrm{x}^k+\mathrm{s}^k$。

子问题的解$\mathrm{s}^k$总是能够使得
$$
f(\mathrm{x}^k+\mathrm{s}^k)\le f(\mathrm{x})
$$

在这个子问题中，如果没有下方的约束，那么求出的二次模型的全局最小值就是牛顿法的值。但这么做无法保证全局收敛。通过某种方法确定信赖域后，可以保证$f(\mathrm{x}^k+\mathrm{s}^k)\le f(\mathrm{x})$。

接下来讨论\key{如何寻找一个合适的$e_k$}。如果值太大，不一定可信赖；如果值太小，则迭代过慢。所以最好还是自适应的调整$e_k$。

\paragraph{如何评价$e_k$}
通过二次模型和目标函数直接的一致程度$r_k$来评价$e_k$是否是一个好的近似。
$$
r_k=\frac{Act_k}{Pre_k}=\frac{f(\mathrm{x}^k)-f(\mathrm{x}^k+\mathrm{s}^k)}{q^k(\mathrm{0})-q^k(\mathrm{s}^k)}
$$

\key{如果}：
\begin{enumerate}
    \item $r_k$接近于1，说明二次模型函数和目标函数的一致性很好，此时可以扩大半径$e_k$。
    \item $r_k>0$但不接近1，维持$e_k$不变。
    \item $r_k$接近于0甚至$r_k<0$，说明一致性不理想，此时要减小半径缩小信赖域。
\end{enumerate}

\subsection{算法框架}
\begin{algorithm}
	\caption{信赖域方法} 
	\begin{algorithmic}[1]
		% 初始化
		\STATE 给定初始点$\mathrm{x}^0$，信赖域半径的上界$\bar{e}$，$\epsilon>0,0<\gamma_1<\gamma_2<1,0<\eta_1<1<\eta_2$。选择$e_0\in(0,\bar{e}),k\leftarrow 0$
        \WHILE[终止条件]{$\mathrm{g}^k \ge \epsilon$}
        \STATE 求解\key{信赖域子问题}，获取$\mathrm{s}^k$
        \STATE 评估信赖域半径：$
        r_k\leftarrow\frac{Act_k}{Pre_k}=\frac{f(\mathrm{x}^k)-f(\mathrm{x}^k+\mathrm{s}^k)}{q^k(\mathrm{0})-q^k(\mathrm{s}^k)}
        $
        \IF[根据评估结果调整迭代点]{$r_k>0$}
            \STATE $\mathrm{x}^{k+1}\leftarrow \mathrm{x}^k+\mathrm{s}^k$
        \ELSE
            \STATE $\mathrm{x}^{k+1}\leftarrow \mathrm{x}^k$
        \ENDIF
        \IF[$r_k$太小]{$r_k<\gamma_1$}
            \STATE $e_{k+1}\leftarrow \eta_1e_k$
        \ELSIF [$r_k$还不错] {$\gamma_1\le r_k<\gamma_2$}
            \STATE $e_{k+1}\leftarrow e_k$
        \ELSIF [$r_k$比较大]{$r_k\ge \gamma_2$}
            \STATE $e_{k+1}\leftarrow\min(\eta_2e_k,\bar{e})$
        \ENDIF
        \STATE $k\leftarrow k+1$
        \ENDWHILE
	\end{algorithmic}
\end{algorithm}

相比线搜索方法，信赖域方法无需关心搜索方向和步长的问题，而是将其变成一个信赖域子问题，并且通过一个评估机制来自适应调整信赖域的半径大小。

下面的算法中使用$\epsilon$作为停机准则，用$\gamma_1,\gamma_2$划分判定$r_k$评估的区间，并且使用$\eta$来缩放信赖域半径。

\section{信赖域子问题求解}
信赖域方法达到全局收敛性的一个条件是子问题必须有精确解。需要有一个比较简单的求解方法。相比牛顿法，信赖域子问题多了一个约束。而根据约束的模数不同，这个子问题又分为不同的情况。这里讨论模数为2的情况。此时问题变成一个含有二次约束的二次目标函数求解的问题。

$$
\begin{aligned}
    \min&\quad q^k(\mathrm{s})=f(\mathrm{x}^k)+(\mathrm{g}^k)^\top\mathrm{s}+\frac{1}{2}\mathrm{s}^\top\mathrm{B}_k\mathrm{s}\\
    s.t.&\quad \lVert \mathrm{s} \lVert\le e_k
\end{aligned}
$$

\subsection{Powell折线法} 这种方法可以快速地求出信赖域子问题的一个非精确的解。

\begin{figure}[H]%
    \centering
    \begin{overpic}[width=0.5\linewidth]{fig/2.1.png}
    \end{overpic}
    \vspace{-3.5mm}
    \vspace{2mm}
\end{figure}

在这张图中，红色的点$\mathrm{x}_c$表示\textbf{柯西点}，是函数在$\mathrm{x}^k$的\key{负梯度方向}的最优解，由于沿着负梯度方向的表达式是单变量的二次函数，所以可以求出一个最优点；蓝色的点$\mathrm{x}_n$表示\textbf{牛顿点}，是函数不考虑约束情况的全局极小点。

$\mathrm{x}_c,\mathrm{x}_n$之间的连线，与二次约束的边界的交点，就是信赖域子问题的近似解。

如果点$\mathrm{x}_c$在信赖域的外侧，那么$\mathrm{x}^k,\mathrm{x}_c$与信赖域边界的交点就是近似解；

如果$\mathrm{x}_n$在信赖域内侧，那么$\mathrm{x}_n$正是需要找的近似点。

\paragraph{性质} 折线法满足一下两条性质，可以解释这么做的合理性。
\begin{enumerate}
    \item 沿着柯西点$\mathrm{x}_c$向牛顿点$\mathrm{x}_n$的连线，到$\mathrm{x}^k$的距离单调增加；
    \item 沿着柯西点$\mathrm{x}_c$向牛顿点$\mathrm{x}_n$的连线，子模型的函数值单调减少。
\end{enumerate}

\subsection{拉格朗日函数法}
可以先求牛顿点，如果牛顿点在可行域中，则将牛顿点作为子问题的解。

否则，可以认为子问题的解在\textbf{约束的边界上}，即$\lVert \mathrm{s} \lVert =e_k$。含有等式约束的约束，可以用拉格朗日函数法解决。


\end{document}